class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n+1,vector<int>(2));
        dp[0][0] = 1;//f[i]->max
        dp[0][1] = 1;//g[i]->min
        for(int i=1;i<=n;i++)
        {
            int x = nums[i-1];
            dp[i][0] = max(x,max(x*dp[i-1][0],x*dp[i-1][1]));
            dp[i][1] = min(x,min(x*dp[i-1][1],x*dp[i-1][0]));
        }
        int ret=dp[1][0];
        for(int i =1;i<=n;i++)
        {
            ret= max(ret,dp[i][0]);
        }
        return ret;
    }
};